package leetcode;

import java.util.Arrays;
import java.util.Comparator;


public class NonOverlappingIntervals {

	public static void main(String[] args) {
		NonOverlappingIntervals object = new NonOverlappingIntervals();
		Interval[] intervals = {new Interval(3, 4), new Interval(2, 7), new Interval(1, 6),
				new Interval(2, 5), new Interval(3, 9), new Interval(5, 6)};
		int res = object.eraseOverlapIntervals(intervals);
		System.out.println(res + "  ");
	}
	
	private static class Interval {
		int start;
		int end;

		Interval() {
			start = 0;
			end = 0;
		}

		Interval(int s, int e) {
			start = s;
			end = e;
		}
	}
	public int eraseOverlapIntervals(Interval[] intervals) {
		if(intervals == null || intervals.length <= 0){
			return 0;
		}
		Arrays.sort(intervals, new Comparator<Interval>() {
			@Override
			public int compare(Interval o1, Interval o2) {
				if(o1.start == o2.start){
					return o1.end - o2.end;
				}
				return o1.start - o2.start;
			}
		});
		int res = 0;
		Interval lastInterval = intervals[0];
		for (int i = 1; i < intervals.length; i++) {
			//如果需要移除
			if(intervals[i].start < lastInterval.end){
				//后来发现贪心策略竟然不对
				//为了保证移除的数目最少，我们总是保证移除间距大的
				//如果相等总是保留end小的
				res++;
				if(intervals[i].end - intervals[i].start < lastInterval.end - lastInterval.start){
					lastInterval = intervals[i];
					System.out.println("remove last: " + lastInterval.start + " " + lastInterval.end);
				}else if(intervals[i].end - intervals[i].start == lastInterval.end - lastInterval.start){
					lastInterval = intervals[i].end < lastInterval.end ? intervals[i] : lastInterval;
					System.out.println("remove " + lastInterval.start  + " " + lastInterval.end);
				}else{
					System.out.println("remove i: " + lastInterval.start + " " + lastInterval.end);
				}
			}else{
				lastInterval = intervals[i];
			}
		}
		return res;
	}
	
	public int eraseOverlapIntervals2(Interval[] intervals) {
		if(intervals == null || intervals.length <= 0){
			return 0;
		}
		Arrays.sort(intervals, new Comparator<Interval>() {
			@Override
			public int compare(Interval o1, Interval o2) {
				if(o1.start == o2.start){
					return o1.end - o2.end;
				}
				return o1.start - o2.start;
			}
		});
		int res = 0;
		Interval lastInterval = intervals[0];
		for (int i = 1; i < intervals.length; i++) {
			//如果需要移除
			if(intervals[i].start < lastInterval.end){
				//为了保证移除的数目最少，我们总是保证移除end小的
				//end小，表示与后面碰撞的概率小
				res++;
				if(intervals[i].end < lastInterval.end){
					lastInterval = intervals[i];
				}
			}else{
				lastInterval = intervals[i];
			}
		}
		return res;
	}
}
